Traditionally, descriptions of Web services have focused primarily on the interfaces that are provided by such services. However, a trend that is gathering momentum is to include, as part of the Web Services Description Language (WSDL), not only the service interface, but also the business protocol supported by the service, i.e., the definition of the ordering constraints on the message exchanges that are allowed by the service, e.g., in interacting with other services. Unfortunately, obtaining a formalized definition of a supported business protocol often is very difficult and time-consuming.